1. Field of the Invention
This invention relates to a method and an apparatus for optimizing an organization of many discrete elements.
2. Description of the Prior Art
Recently, computers have been used to derive an optimal organization of discrete elements. In respect of a group of a small number of discrete elements, it has been possible to determine an optimal organization, which satisfies an objective specification, by examining all possible organizations which the element group can take. However, the method including the process of examining all possible organizations tends to be impractical in determining an optimal organization of a large number of discrete elements with many constraints because the number of the possible organizations exponentially increases and a CPU cost greatly increases with increases in the numbers of the elements and the constraints. In the field where an optimal organization of many discrete elements affects the usefulness of designing, such an increase in the CPU cost causes problems that a time spent in the designing is long and a computer cost is high.
Such an optimization of an organization of many discrete elements is necessary for the resolution of a cell assignment problem of a logical functional element mask (a cell element mask) in circuit mask layout of the standard-cell type or the gate-array type in the fabrication of a semiconductor device. In the standard-cell layout method or the gate-array layout method, an optimal assignment organization of a group of cell elements which satisfies an objective specification of LSI mask layout must be determined by using previously-prepared cell element groups composing a device to be formed on a semiconductor substrate, and by using logical net information representing the relation among the cell element groups. The objective specification of LSI mask layout means the determination of a cell element assignment organization which satisfies a plurality of conditions such as a minimization of the chip area size and a minimization of the estimated total wire length. In respect of a cell element group having 20,000 or more elements, a cell assignment problem in the standard-cell layout method or the gate-array layout method can not be easily resolved by examining all possible organizations to determine an optimal organization. Accordingly, an inexpensive and quick optimization of an organization has been desired in such a large number of discrete elements.
U.S. Pat. No. 3,654,615 relates to an element placement system in which a first element organization is modified into a second element organization; an objective function value representing the degree of the nearness of the second element organization to an objective specification is calculated; the objective function value is examined to determine whether or not an improvement is present; and such processes are repeated to find an element organization well matching to the objective specification. In general, the element organization which is obtained through the repetition of a local change is far from an objective specification than the element organization which is obtained through the repetition of a global change is. In U.S. Pat. No. 3,654,615, since the improvement of an element organization is performed through only local changes, a finally-obtained element organization tends to be inferior to a final element organization tends to be inferior to a final element organization obtained through global changes.
U.S. Pat. No. 4,495,559 relates to an optimization of an organization of discrete elements which considers a global element organization. In U.S. Pat. No. 4,495,559, an attention is paid to a natural phenomenon of annealing in which an organization of atoms and molecules of a substance gradually changes from a disordered state to an energy-lowest ground state during the gradually cooling (annealing) of the substance from a high temperature state to a low temperature state. In addition, U.S. Pat. No. 4,495,559 uses the fact that a computer simulation can reproduce such a phenomenon. In the optimization of U.S. Pat. No. 4,495,559, elements are regarded as atoms or molecules composing the substance, and the objective function, which enables the degree of the nearness to an objective specification to be represented by a numeral value, is regarded as energy. Since the minimization of energy is caused in dependence upon the global conditions of the substance, the optimization of U.S. Pat. No. 4,495,559 considers a global aspect of the element organization. Since such a method of simulated annealing can be applied to a substance having any complicated factors, the method considers a global aspect of the element organization rather than a local aspect and can obtain an excellent optimal organization regardless of the type of a constraint and the number of elements. A temperature parameter and a cooling schedule parameter greatly affect a finally-obtained element organization in the method of simulated annealing. The cooling schedule parameter determines a rate at which the temperature parameter is lowered. A heat equilibrium state is used as a reference for judging conditions of processes at respective temperatures which enable changes of the temperatures to next values. The optimization of U.S. Pat. No. 4,495,559 has difficulty in determining the temperature parameter and the cooling schedule parameter, and establishing the heat equilibrium state. Various computer simulations teach the following facts. To derive an element organization which satisfies an objective specification, it is necessary that an initial temperature parameter is set as high as possible, and a final temperature parameter is set as low as possible, and that a cooling schedule parameter is set close to 1 so as to lower the temperature as slow as possible. As understood from the previous description, the optimization of U.S. Pat. No. 4,495,559 tends to require a very high CPU cost. Furthermore, according to the optimization of U.S. Pat. No. 4,495,559, it is generally difficult to confirm that the processing is performed under optimal conditions.